package com.qz.linkedlist;


import java.util.Stack;

/**
 * @Description 单链表面试题
 * @Author Flag
 * @Date: 2021/7/4 17:29
 * @Version: 1.0
 **/
public class SingleLinkedListInterview {
    public static void main(String[] args) {


        //先创建节点
        HeroNode hero1 = new HeroNode(5, "马超", "孟奇");
        HeroNode hero2 = new HeroNode(1, "关羽", "云长");
        HeroNode hero3 = new HeroNode(3, "赵云", "子龙");
        HeroNode hero4 = new HeroNode(2, "张飞", "翼德");
        HeroNode hero5 = new HeroNode(4, "黄忠", "汉生");


        //先创建节点
        HeroNode hero6 = new HeroNode(6, "张辽", "文远");
        HeroNode hero7 = new HeroNode(7, "徐晃", "共明");
        HeroNode hero8 = new HeroNode(8, "张郃", "俊艾");
        HeroNode hero9 = new HeroNode(9, "乐进", "文谦");
        HeroNode hero10 = new HeroNode(10, "于禁", "文则");





        //创建一个链表
        SingleLinkedList singleLinkedList = new SingleLinkedList();
        singleLinkedList.addByOrder(hero5);
        singleLinkedList.addByOrder(hero3);
        singleLinkedList.addByOrder(hero1);
        singleLinkedList.addByOrder(hero2);
        singleLinkedList.addByOrder(hero4);
        singleLinkedList.addByOrder(hero6);
        singleLinkedList.addByOrder(hero7);

        SingleLinkedList singleLinkedList2 = new SingleLinkedList();
        singleLinkedList2.addByOrder(hero8);
        singleLinkedList2.addByOrder(hero9);
        singleLinkedList2.addByOrder(hero10);

        //测试1:  getLength 获取到单链表的节点的个数
//        System.out.println("有效的节点个数=" + getLength(singleLinkedList.getHead()));

        //测试2：
//        System.out.println(findLastIndexNode(singleLinkedList.getHead(), 10));


//        singleLinkedList.show();

        //测试3:
//        reversetList(singleLinkedList.getHead());
//        singleLinkedList.show();

        //测试4
//        reversetPrint(singleLinkedList.getHead());

        //测试5:
        mergeLinkedList(singleLinkedList.getHead(),singleLinkedList2.getHead()).show();
    }

    /**
     * 方法：获取到单链表的节点的个数（如果是带头节点的链表，需要不统计头节点）
     * @param head 链表的头节点
     * @return 返回的就是有效节点的个数
     */
    public static int getLength(HeroNode head){
        //如果是空链表，直接返回
        if(head.next == null){
            return 0;
        }
        int length = 0;
        //定义一个辅助变量，这里我们没有统计头节点
        HeroNode temp = head;
        while ((temp = temp.next) != null){
            length++;
        }
        return length;
    }


    /**
     * 查找单链表中的倒数第k个结点 【新浪面试题】
     * 1.编写一个方法，接收head节点，同时接收一个indxe
     * 2.index表示倒数的第index个节点
     * 3.先把链表从头到尾巴遍历，得到链表的总长度getLength
     * 4.得到size止呕，我们从链表的第一个开始遍历，size-index个，就可以得到
     * 5.如果找到，则返回该节点，否则返回null
     *
     * @param head 头节点
     * @param index 倒数第k个节点
     * @return
     */
    public static HeroNode findLastIndexNode(HeroNode head,int index){
        //判断链表是否为null
        if(head.next == null){
            return null;
        }
        //通过第一次遍历，获取链表的长度
        int size = getLength(head);
        //校验形参index是否合法
        if(index <= 0 ||  index > size){
            return null;
        }
        //定义辅助变量，存储遍历过程中的各个节点
        HeroNode temp = head.next;
        //遍历，将倒数的index节点，变成正数的编号，进行遍历，然后获取
        for (int i = 0 ; i < size - index ; i++){
            temp = temp.next;
        }
        return temp;
    }


    /**
     * 从尾到头打印单链表 【百度，要求方式1：反向遍历 。 方式2：Stack栈】
     * @param head
     */
    public static void reversetList(HeroNode head){
        //1.判断链表是否为null,或者只有一个节点，直接返回
        if(head.next == null || head.next.next == null){
            return;
        }
        //定义一个辅助的指针(变量),帮助我们遍历原来的链表
        HeroNode temp = head.next;
        //指向当前节点[temp]的next节点
        HeroNode next = null;
        //定义一格反转链表的头节点
        HeroNode reverseHead = new HeroNode(0,"","");
        //遍历原始数组的每一个元素,将其取出，并放到新的链表reverseHead的最前端
        while (temp != null){
            //拿到temp的next节点
            next = temp.next;
            //1.先将摘下来的元素，添加到新链表最前端
            temp.next = reverseHead.next;
            //将temp链接到新的链表上
            reverseHead.next = temp;
            //让cur后移
            temp = next;
        }
        //将head.next指向reverseHead.next，实现链表的反转
        head.next = reverseHead.next;
    }


    /**
     * 可以利用栈这个数据结构，将各个节点压入到栈中，然后利用栈的先进后出的特点,就实现了逆序打印的结果
     * @param head
     */
    public static void reversetPrint(HeroNode head){
        //判断单链表是否为null
        if(head.next == null){
            return;
        }
        //定义一个中间遍历，存放链表的节点信息
        HeroNode temp = head.next;

        //定义一个栈存放信息
        Stack<HeroNode> stack = new Stack<>();

        //将遍历单链表，将单链表放入到栈中
        while (temp != null){
            //将元素添加到栈中
            stack.add(temp);
            //继续遍历下一个元素
            temp = temp.next;
        }
        //将栈中饿节点打印，pop出栈
        while (stack.size()>0){
            //stack特点是先进后出
            System.out.println(stack.pop());
        }
    }


    /**
     * 合并两个有序的单链表，合并之后的链表依然有序【课后练习.】
     * 两个升序链表合成一个升序链表
     * 如果出现两个链表节点的node相同,则先添加链表1的节点,在添加链表2的节点
     * @param head1 链表1的头节点
     * @param head2 链表2的头节点
     * @return 返回合并后的结果链表
     */
    public static SingleLinkedList mergeLinkedList(HeroNode head1,HeroNode head2){
        //1.判断链表1和链表是否为null,如果为null,直接退出
        if(head1.next == null && head2.next == null){
            return null;
        }
        //定义两个中间遍历
        HeroNode temp1 = head1.next;
        HeroNode temp2 = head2.next;
        //定义返回的集合
        SingleLinkedList mergoList = new SingleLinkedList();
        //定义返回的节点
        HeroNode mergoNode = mergoList.getHead();
        //遍历两个链表
        while (!(temp1 == null && temp2 == null)){

            if(temp1 == null){
                /**
                 * 如果链表1为null,则只将链表2合并集合
                 */

                //将链表2的节点放到返回结果的链表上
                mergoNode.next = temp2;
                //移动链表2至下一个节点
                temp2 = temp2.next;
                //返回结果的链表移动到至下一个节点
                mergoNode = mergoNode.next;

            } else if(temp2 == null){
                /**
                 * 如果链表2为null,则只将链表1合并到结合中
                 */

                //将链表1的节点放到返回结果的链表上
                mergoNode.next = temp1;
                //移动链表1至下一个节点
                temp1 = temp1.next;
                //移动合并后的链表节点至下一个节点
                mergoNode = mergoNode.next;
            } else {
                /**
                 * 进入到这里,证明temp1和temp2的链表都不是null
                 */

                if(temp1.no > temp2.no){
                    /**
                     * 如果temp1大于temp2.则将temp2放入到链表中
                     */
                    //将链表2节点放到返回结果的链表上
                    mergoNode.next = temp2;
                    //移动链表2到下一个节点
                    temp2 = temp2.next;
                    //返回结果的链表节点向后移动
                    mergoNode = mergoNode.next;
                } else if(temp1.no < temp2.no){
                    /**
                     * 如果temp1小于temp2，将temp1放入到链表中
                     */
                    //将链表2的节点放到返回结果的链表上
                    mergoNode.next = temp1;
                    //移动链表1到下一个节点
                    temp1 = temp1.next;
                    //返回结果的链表节点向后移动
                    mergoNode = mergoNode.next;
                } else {
                    /**
                     * 如果链表1节点的no==链表2的节点的no,则先将链表1放入，在将链表2放入
                     */
                    //将链表1的节点放到返回结果的链表上
                    mergoNode.next = temp1;
                    //将链表1的节点后移动
                    temp1 = temp1.next;
                    //将链表2的节点放到返回结果链表的下一个节点的下一个节点：即组成：返回节点链表的节点->temp1->temp2
                    mergoNode.next.next = temp2;
                    //将链表2的节点后移动
                    temp2 = temp2.next;
                    //将返回结果的链表节点向后移动
                    mergoNode = mergoNode.next;
                }
            }
        }
        //返回合并后的目标链表
        return mergoList;


    }




}
